﻿#include "stdafx.h"
#include "HammingDistance.h"

using namespace std;

namespace algorithm {
int CHammingDistance::Distance(int x, int y)
{
    // Brian Kernighan算法
    // nxor=x^y        10001000
    // nxor-1          10000111
    // nxor & (nxor-1) 10000000
    // 一次操作，将nxor的最右边的1变为0，反复操作，直到nxor为0
    int nxor = x ^ y;
    int distance = 0;
    while (nxor!= 0) {
        distance++;
        nxor &= (nxor - 1);
    }
    return distance;
}
int CHammingDistance::Distance2(int x, int y)
{
    int distance = 0;
    while (x != 0 || y != 0) {
        distance += (x & 1) ^ (y & 1);
        x >>= 1;
        y >>= 1;
    }
    return distance;
}
}
